package com.duoduo.剑指Offer;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 连续子数组的最大和17
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 要求时间复杂度为O(n)。
 *
 *  
 *
 * 示例1:
 *
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 *              -2,1,-2,4,3,5,6,1,5
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 *
 * @author: chaidl  ！
 * @create: 2022-05-24 22:43
 */
public class 连续子数组的最大和17 {
	public static void main(String[] args) {
		int[] arr={-2,1,-3,4,-1,2,1,-5,4};
		maxSubArray(arr);
	}
	public static  int maxSubArray(int[] nums) {
		int result=nums[0];
		int pre=result;
		for (int i = 1; i < nums.length; i++) {
			//如果第一个数+第二个数大于第二个数，那么pre就是最大的那个数
			pre=Math.max(pre+nums[i],nums[i]);
			if (pre >result){
				result = pre;
			}
		}
		return result;
	}
	public int maxSubArray1(int[] nums) {
	//	初始化一个dp数组
		int[] dp=new int[nums.length];
		dp[0]=nums[0];
		//int pre=dp[0];
		int result=dp[0];
		//从第一个位置开始
		for (int i = 1; i < nums.length; i++) {
			//如果dp元素+当前元素>当前元素，则dp[i]放入的就是比较大的值
			dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
			//如果此时的值比最大值打，记录一下
			if (dp[i] >result){
				result = dp[i];
			}
		}
		return result;
	}
}
